package main

/*
链表相交/两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

//哈希表
func getIntersectionNode1(headA, headB *ListNode) *ListNode {
	vis := map[*ListNode]bool{}                    //建立一个链表的哈希
	for tmp := headA; tmp != nil; tmp = tmp.Next { //遍历headA链表 将其加入到hash中
		vis[tmp] = true
	}
	for tmp := headB; tmp != nil; tmp = tmp.Next {
		if vis[tmp] { //如果哈希中存在相同的链表节点
			return tmp //返回该节点
		}
	}
	//否则没有相交节点 返回空
	return nil
}

//双指针
func getIntersectionNode2(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	la, lb := headA, headB
	for la != lb { //当la ！= lb时
		if la == nil {
			la = headB //当la为空的时候，指向headB
		} else {
			la = la.Next
		}
		if lb == nil {
			lb = headA //当lb为空的时候，指向headA
		} else {
			lb = lb.Next
		}
		//如果有公共节点 迟早会相交 la == lb
	}
	return la
}

//我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，
//此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
//否则循环退出返回空指针。
func getIntersectionNode3(headA, headB *ListNode) *ListNode {
	curA := headA
	curB := headB
	lenA, lenB := 0, 0
	// 求A，B的长度
	for curA != nil {
		curA = curA.Next
		lenA++
	}
	for curB != nil {
		curB = curB.Next
		lenB++
	}
	var step int
	var fast, slow *ListNode
	// 请求长度差，并且让更长的链表先走相差的长度
	if lenA > lenB {
		step = lenA - lenB
		fast, slow = headA, headB
	} else {
		step = lenB - lenA
		fast, slow = headB, headA
	}
	for i := 0; i < step; i++ {
		fast = fast.Next
	}
	// 遍历两个链表遇到相同则跳出遍历
	for fast != slow {
		fast = fast.Next
		slow = slow.Next
	}
	return fast
}
